#include <iostream>
#include <string>
#include <bitset>
#include <cmath>
#include <vector>
#include <sstream>
#include <iomanip>
#include <stdexcept>
#include <algorithm>

using namespace std;

// 枚举类型定义
enum class LatDirection
{
    S,
    N
};
enum class LngDirection
{
    W,
    E
};

// 基本数据结构定义
struct DecodeOption
{
    string form;
    DecodeOption(const string &f) : form(f) {}
};

// 方向解码相关实现
class Direction
{
public:
    LngDirection lngDir;
    LatDirection latDir;

    Direction(LngDirection lng, LatDirection lat)
        : lngDir(lng), latDir(lat) {}
};

struct LngLat
{
    double lngDegree = 0.0;
    double lngMinute = 0.0;
    double lngSecond = 0.0;
    LngDirection lngDirection = LngDirection::E;

    double latDegree = 0.0;
    double latMinute = 0.0;
    double latSecond = 0.0;
    LatDirection latDirection = LatDirection::N;

    LngLat() = default;
    LngLat(double lng, double lat) : lngDegree(lng), latDegree(lat) {}

    string getLngStr() const
    {
        stringstream ss;
        ss << lngDegree << "° " << lngMinute << "' " << fixed << setprecision(6)
           << lngSecond << "\" " << (lngDirection == LngDirection::E ? "E" : "W");
        return ss.str();
    }

    string getLatStr() const
    {
        stringstream ss;
        ss << latDegree << "° " << latMinute << "' " << fixed << setprecision(6)
           << latSecond << "\" " << (latDirection == LatDirection::N ? "N" : "S");
        return ss.str();
    }

    friend ostream &operator<<(ostream &os, const LngLat &ll)
    {
        os << "经度：" << ll.getLngStr() << ", 纬度：" << ll.getLatStr();
        return os;
    }
};

struct LngLatEle : public LngLat
{
    double elevation = 0.0;

    LngLatEle() = default;
    LngLatEle(double lng, double lat, double ele = 0)
        : LngLat(lng, lat), elevation(ele) {}
    LngLatEle(const LngLat &ll, double e) : LngLat(ll), elevation(e) {}

    friend ostream &operator<<(ostream &os, const LngLatEle &lle)
    {
        os << static_cast<const LngLat &>(lle) << " 高度:" << fixed << setprecision(6) << lle.elevation;
        return os;
    }
};

// 网格数据常量
namespace GridData
{
    const vector<vector<double>> gridSizes1 = {
        {1, 1},
        {21600, 14400},
        {1800, 1800},
        {900, 600},
        {60, 60},
        {4, 4},
        {2, 2},
        {0.25, 0.25},
        {0.03125, 0.03125},
        {0.00390625, 0.00390625},
        {0.00048828125, 0.00048828125}};

    const vector<vector<int>> gridCountPole = {
        {1, 1},
        {1, 1},
        {4, 4},
        {2, 2},
        {15, 15},
        {15, 15},
        {2, 2},
        {8, 8},
        {8, 8},
        {8, 8},
        {8, 8}};

    const vector<vector<int>> elevationParams = {
        {1, 2},
        {6, 10},
        {3, 8},
        {1, 2},
        {4, 16},
        {4, 16},
        {1, 2},
        {3, 8},
        {3, 8},
        {3, 8},
        {3, 8}};

    const vector<int> codeLengthAtLevel = {1, 4, 6, 7, 9, 11, 12, 14, 16, 18, 20};
}

// 辅助函数
namespace Codec2DUtils
{
    pair<double, double> getSecond(const LngLat &lngLat)
    {
        // 实现与Java版本相同的秒数转换逻辑
        double lngInSec = (lngLat.lngDegree * 3600 + lngLat.lngMinute * 60 + lngLat.lngSecond) *
                          (lngLat.lngDirection == LngDirection::W ? -1 : 1);

        double latInSec = (lngLat.latDegree * 3600 + lngLat.latMinute * 60 + lngLat.latSecond) *
                          (lngLat.latDirection == LatDirection::S ? -1 : 1);

        return {lngInSec, latInSec};
    }

    string encodeFragment(int level, int lngCount, int latCount)
    {
        if (level == 3 || level == 6)
        {
            return to_string(latCount * 2 + lngCount);
        }
        else if (level > 1 && level <= 10)
        {
            stringstream ss;
            ss << hex << uppercase << lngCount << latCount;
            return ss.str();
        }
        else if (level == 1)
        {
            stringstream ss;
            ss << setw(2) << setfill('0') << lngCount
               << static_cast<char>('A' + latCount);
            return ss.str();
        }
        throw invalid_argument("非法层级 level");
    }
}

namespace LocationCodeUtils
{
    // 辅助方法实现
    int getCodeLevel(const string &code)
    {
        static const vector<int> codeLen = {1, 4, 6, 7, 9, 11, 12, 14, 16, 18, 20};
        auto it = find(codeLen.begin(), codeLen.end(), code.length());
        if (it == codeLen.end())
            throw runtime_error("Invalid code length");
        return distance(codeLen.begin(), it);
    }

    Direction getDirections(const string &code)
    {
        LatDirection lat = (code[0] == 'N') ? LatDirection::N : LatDirection::S;
        int lngPart = stoi(code.substr(1, 2));
        LngDirection lng = (lngPart >= 31) ? LngDirection::E : LngDirection::W;
        return Direction(lng, lat);
    }

    vector<int> getSigns(const Direction &dir)
    {
        return {
            dir.lngDir == LngDirection::E ? 1 : -1,
            dir.latDir == LatDirection::N ? 1 : -1};
    }

    vector<int> getRowAndCol(const string &fragment, int level)
    {
        if (level == 1)
        {
            int lng = stoi(fragment.substr(0, 2));
            int lat = fragment[2] - 'A';
            return {lng, lat};
        }
        if (level == 3 || level == 6)
        {
            int num = stoi(fragment);
            return {num % 2, num / 2};
        }
        if (level >= 2 && level <= 10)
        {
            return {
                stoi(fragment.substr(0, 1), 0, 16),
                stoi(fragment.substr(1, 1), 0, 16)};
        }
        return {0, 0};
    }

    string getCodeAtLevel(const string &code, int level)
    {
        static const vector<int> lenMap = {1, 4, 6, 7, 9, 11, 12, 14, 16, 18, 20};
        if (level == 0)
            return string(1, code[0]);
        int start = lenMap[level - 1];
        return code.substr(start, lenMap[level] - start);
    }
};

// Codec2D 类实现
class Codec2D
{
public:
    static string encode(const LngLat &lngLat, int level = 10)
    {
        const auto &sec = Codec2DUtils::getSecond(lngLat);
        string code;
        double lngInSec = sec.first;
        double latInSec = sec.second;
        double lngN = 0, latN = 0;

        if (abs(lngLat.latDegree) >= 88)
        {
            // 极区编码逻辑
            // 此处简化实现，完整实现需要补充PoleGrid等相关类
            throw runtime_error("极区编码暂未实现");
        }
        else
        {
            for (int i = 0; i <= level; ++i)
            {
                auto res = encodeN(lngInSec, latInSec, lngN, latN, i);
                lngN += res.lngNP1;
                latN += res.latNP1;
                code += res.codeN;
                if (i == 1)
                {
                    lngInSec = abs(lngInSec);
                    latInSec = abs(latInSec);
                }
            }
        }
        return code;
    }

    static LngLat decode(const string &code, const DecodeOption &opt = DecodeOption("dms"))
    {
        int level = LocationCodeUtils::getCodeLevel(code);
        Direction dir = LocationCodeUtils::getDirections(code);
        auto signs = LocationCodeUtils::getSigns(dir);

        double totalLngSec = 0;
        double totalLatSec = 0;

        for (int i = 1; i <= level; ++i)
        {
            auto offsets = decodeN(code, i);
            totalLngSec += offsets[0];
            totalLatSec += offsets[1];
        }

        return buildResult(totalLngSec, totalLatSec, signs, opt);
    }

private:
    struct NPole
    {
        double lngNP1;
        double latNP1;
        string codeN;

        NPole(double lng, double lat, const string &code)
            : lngNP1(lng), latNP1(lat), codeN(code) {}
    };

    static NPole encodeN(double lngInSec, double latInSec, double lngN, double latN, int n)
    {
        if (n == 0)
        {
            return {0, 0, latInSec > 0 ? "N" : "S"};
        }
        else if (n == 1)
        {
            int a = floor(lngInSec / GridData::gridSizes1[1][0]);
            int b = floor(abs(latInSec) / GridData::gridSizes1[1][1]);
            return {a * GridData::gridSizes1[1][0],
                    b * GridData::gridSizes1[1][1],
                    Codec2DUtils::encodeFragment(1, a + 31, b)};
        }
        else
        {
            int a = floor((lngInSec - lngN) / GridData::gridSizes1[n][0]);
            int b = floor((latInSec - latN) / GridData::gridSizes1[n][1]);
            return {a * GridData::gridSizes1[n][0],
                    b * GridData::gridSizes1[n][1],
                    Codec2DUtils::encodeFragment(n, a, b)};
        }
    }

    static vector<double> decodeN(const string &code, int n)
    {
        string fragment = LocationCodeUtils::getCodeAtLevel(code, n);
        auto rc = LocationCodeUtils::getRowAndCol(fragment, n);
        // 如果是第一级，需要特殊处理
        if (n == 1)
        {
            if (rc[0] == 0)
            {
                // throw new IllegalArgumentException("暂不支持解码两极地区(纬度大于等于88°)编码");
            }
            rc[0] = rc[0] >= 31 ? rc[0] - 31 : 30 - rc[0];
        }
        double lngSec = rc[0] * GridData::gridSizes1[n][0];
        double latSec = rc[1] * GridData::gridSizes1[n][1];
        return {lngSec, latSec};
    }

    static LngLat buildResult(double lngSec, double latSec,
                              const vector<int> &signs,
                              const DecodeOption &opt)
    {
        LngLat result;

        // 设置方向
        result.lngDirection = (signs[0] > 0) ? LngDirection::E : LngDirection::W;
        result.latDirection = (signs[1] > 0) ? LatDirection::N : LatDirection::S;

        if (opt.form == "decimal")
        {
            result.lngDegree = lngSec * signs[0] / 3600.0;
            result.latDegree = latSec * signs[1] / 3600.0;
        }
        else
        {
            setDMS(result.lngDegree, result.lngMinute, result.lngSecond,
                   lngSec * signs[0]);
            setDMS(result.latDegree, result.latMinute, result.latSecond,
                   latSec * signs[1]);
        }
        return result;
    }

    static void setDMS(double &degree, double &minute, double &second, double totalSec)
    {
        degree = floor(totalSec / 3600);
        double remain = fmod(totalSec, 3600);
        minute = floor(remain / 60);
        second = fmod(remain, 60);
    }
};

namespace GridData3D
{
    const vector<vector<int>> elevationParams = {
        {1, 2},  // 级别0
        {6, 10}, // 级别1
        {3, 8},  // 级别2
        {1, 2},  // 级别3
        {4, 16}, // 级别4
        {4, 16}, // 级别5
        {1, 2},  // 级别6
        {3, 8},  // 级别7
        {3, 8},  // 级别8
        {3, 8},  // 级别9
        {3, 8}   // 级别10
    };
}

class Codec3D
{
public:
    // 编码入口
    static string encode(const LngLatEle &point, double r = 6378137, int level = 10)
    {
        string code2d = Codec2D::encode(point, level);
        string codeEle = encodeElevation(point.elevation, r, level);
        return code2d + codeEle;
    }

    // 解码入口
    static LngLatEle decode(const string &code, double r = 6378137)
    {
        if (code.length() != 32)
            throw invalid_argument("编码长度必须为32位");

        string code2d = code.substr(0, 20);
        string codeEle = code.substr(20, 12);

        LngLat base = Codec2D::decode(code2d);
        double elevation = decodeElevation(codeEle, r);

        return LngLatEle(base, elevation);
    }

private:
    // 高程编码核心算法
    static string encodeElevation(double h, double r, int level)
    {
        const double theta = 1.0 / (2048 * 3600);
        const double theta0 = 1.0;

        int n = floor((theta0 / theta) *
                      (log((h + r) / r) / log(1 + theta0 * (M_PI / 180))));

        // 生成32位二进制字符串
        string binStr = bitset<32>(abs(n)).to_string();
        if (n < 0)
            binStr[0] = '1';

        // 分段编码
        return encodeElevationFragments(binStr, level);
    }

    // 分段编码处理
    static string encodeElevationFragments(const string &binStr, int level)
    {
        stringstream code;
        int index = 0;

        for (int i = 0; i <= level; ++i)
        {
            int bits = GridData3D::elevationParams[i][0];
            int base = GridData3D::elevationParams[i][1];

            string part = binStr.substr(index, bits);
            index += bits;

            // 二进制转目标进制
            int value = stoi(part, 0, 2);
            code << formatFragment(value, base, i);
        }
        return code.str();
    }

    // 格式化工件
    static string formatFragment(int value, int base, int level)
    {
        stringstream ss;
        ss << uppercase << setbase(base) << value;

        string s = ss.str();
        // 特殊处理级别1需要两位
        if (level == 1 && s.length() < 2)
            s = string(2 - s.length(), '0') + s;

        return s;
    }

    // 高程解码核心算法
    static double decodeElevation(const string &code, double r)
    {
        string binStr = decodeElevationFragments(code);

        // 处理符号位
        int sign = (binStr[0] == '0') ? 1 : -1;
        int n = sign * stoi(binStr.substr(1), 0, 2);

        const double theta = 1.0 / (2048 * 3600);
        const double theta0 = 1.0;

        return pow(1 + theta0 * (M_PI / 180), n * (theta / theta0)) * r - r;
    }

    // 分段解码处理
    static string decodeElevationFragments(const string &code)
    {
        stringstream binStr;
        binStr << (code[0] == '0' ? '0' : '1'); // 符号位

        // 处理第一级
        int level1 = stoi(code.substr(1, 2), 0, 10);
        binStr << bitset<6>(level1).to_string();

        // 处理后续级别
        for (int i = 2; i <= 10; ++i)
        {
            int bits = GridData3D::elevationParams[i][0];
            int base = GridData3D::elevationParams[i][1];

            string part(1, code[i + 1]); // 字符位置需要调整
            int value = stoi(part, 0, base);
            binStr << bitset<4>(value).to_string().substr(4 - bits);
        }

        return binStr.str();
    }
};

// 测试主函数
int main()
{
    LngLat testPoint;
    testPoint.lngDegree = 116.306; // 示例经度
    testPoint.latDegree = 39.976;  // 示例纬度

    string code = Codec2D::encode(testPoint);
    cout << "北斗二维网格编码: " << code << endl;

    string code1 = "N50J47539B82"; // 示例编码

    // 解码测试
    LngLat position = Codec2D::decode(code1);
    cout << "解码结果（度分秒）:\n"
         << position << endl;

    // 小数格式解码
    LngLat decPosition = Codec2D::decode(code1, DecodeOption("decimal"));
    cout << "解码结果（小数）:\n"
         << decPosition.lngDegree << "°, "
         << decPosition.latDegree << "°" << endl;

    // 编码测试
    LngLatEle point(116.3975, 39.9087, 50.5);
    string code3d = Codec3D::encode(point);
    cout << "三维编码结果：" << code3d << endl;

    // 解码测试
    LngLatEle decoded = Codec3D::decode(code3d);
    cout << "解码结果：" << decoded.lngDegree << ", "
         << decoded.latDegree << ", " << decoded.elevation << endl;

    // 精度测试
    cout << "高程误差：" << abs(50.5 - decoded.elevation) << "米" << endl;

    return 0;
}
